package datastruct;

import java.util.LinkedList;
import java.util.Queue;

public class MaxSlidingWindow {

    /**
     * LeetCode T239 滑动窗口最大值
     * 总结：使用单调队列 + 延迟删除
     * @param args
     */
    public static void main(String[] args) {

    }

    public int[] maxSlidingWindow(int[] nums, int k){
        int len = nums.length;
        if (len < k){
            return null;
        }
        int[] res = new int[len - k + 1];
        LinkedList<int[]> queue = new LinkedList<>();
        //进行初始化
        for (int i = 0; i < k; i++){
            while (!queue.isEmpty()){
                if (queue.getLast()[0] < nums[i]){
                    queue.removeLast();
                } else {
                    break;
                }
            }
            queue.addLast(new int[]{nums[i], i});
        }
        res[0] = queue.getFirst()[0];
        for (int i = k; i < len; i++){
            while (!queue.isEmpty()){
                if (queue.getLast()[0] < nums[i]){
                    queue.removeLast();
                } else {
                    break;
                }
            }
            queue.addLast(new int[]{nums[i], i});
            while (queue.getFirst()[1] < i - k + 1){
                queue.removeFirst();
            }
            res[i - k + 1] = queue.getFirst()[0];
        }
        return res;

    }
}
